home *** CD-ROM | disk | FTP | other *** search
/ Amiga Packmags / Source, The - Issue 5 (1993)(Epsilon)[WB].zip / Source, The - Issue 5 (1993)(Epsilon)[WB].adf / Source / Vectors / VectorSpace / PointsInCircle.lha / pointsncircle1.txt next >
Internet Message Format  |  1989-10-24  |  2KB
  1. From albanycs!leah:rsb584 Wed Apr  6 17:31:10 1988
  2. Received: by albanycs.albany.edu (5.54/4.8)
  3.     id AA28062; Wed, 6 Apr 88 11:55:28 EST
  4. Date: Wed, 6 Apr 88 12:55:21 EDT
  5. From: albanycs!leah:rsb584 (Raymond S Brand)
  6. Received: by leah.Albany.EDU (5.58/1.1)
  7.     id AA02143; Wed, 6 Apr 88 12:55:21 EDT
  8. Message-Id: <8804061655.AA02143@leah.Albany.EDU>
  9. To: albanycs:beowulf!rsbx
  10. Subject: circle.txt
  11.  
  12. >From roy@phri.UUCP Fri Apr  1 10:37:17 1988
  13. Path: leah!uwmcsd1!bbn!rochester!cornell!uw-beaver!mit-eddie!husc6!cmcl2!phri!roy
  14. From: roy@phri.UUCP (Roy Smith)
  15. Newsgroups: comp.graphics
  16. Subject: Re: Algorithm wanted: Circle enclosing points
  17. Message-ID: <3226@phri.UUCP>
  18. Date: 1 Apr 88 15:37:17 GMT
  19. References: <wWIfSMy00Xo3A5u1dC@andrew.cmu.edu>
  20. Reply-To: roy@phri.UUCP (Roy Smith)
  21. Organization: Public Health Research Inst. (NY, NY)
  22. Lines: 24
  23.  
  24. mp1u+@andrew.cmu.edu (Michael Portuesi) writes:
  25. > I am looking for an efficient algorithm that, given a set of points, finds
  26. > the smallest circle enclosing them and its center.
  27.  
  28. Take a look at:
  29.  
  30. %A R. Sedgewick
  31. %T Algorithms
  32. %D 1983
  33. %I Addison-Wesley
  34. %C Reading, Mass.
  35.  
  36. Chapter 25 (Finding the Convex Hull) is devoted to the problem of finding
  37. the smallest convex polygon which encloses a set of points (in a plane,
  38. which I assume is what you're talking about).  Once you have that, it seems
  39. intuitively obvious (i.e. I havn't actually sat down to prove it) that
  40. you've at least narrowed the problem down a lot.  For example, at least 2
  41. of the verticies of the convex hull must lie on the circle (consider 3
  42. points which form an equilateral triangle; all three lie on the circle).
  43. Hope this helps.
  44. -- 
  45. Roy Smith, {allegra,cmcl2,philabs}!phri!roy
  46. System Administrator, Public Health Research Institute
  47. 455 First Avenue, New York, NY 10016
  48.  
  49.  
  50.